// Copyright 2011 Noam and Georges and all that
#ifndef _VLENCODE_H_
#define _VLENCODE_H_ 


#include "util.h"
#include "bitarray.h"

struct SimpleCorpus {
  bool Load(string fn);
  void Store(string fn);
  uint64 size() { return size_; } 
  uint32 operator [](uint64 n) { return data_[n]; }
  void StartBuild(uint64 max_size);
  void Push(uint32 n);
  void EndBuild(); 
  void DistributedTouch();

  Memblock GetMemblock();

  uint64 size_;
  uint32 * data_;
  uint64 max_size_;
};

/* 
   A crazy ass variable length encoding of a sequence of uint64s that allows for 
   dense random access.
   2^64-1 cannot be encoded in this scheme.  

   We break each uint64 into a 6 bit exponent and a variable-length mantissa. 
   The exponents are stored in blocks, and the mantissas in a big bit vector. 
 */

// the position of the most significant 1 in a positive uint64
inline uint32 GetExponent(uint64 n) {
  double d = n;
  uint64 int_d = *((uint64 *)&d);
  return ( (int_d >> 52) & 0x7FFull ) - 1023; }

// the corresponding mantissa, given the exponent. 
inline uint64 GetManitssa(uint64 n, uint64 x) {
  return n - (1ull << x); }

// convert n into an exponent x and mantissa m
inline void VariableEncode(uint64 n, uint32 * fixed, uint64 * variable) {
  n++;
  *fixed = GetExponent(n);
  *variable = GetManitssa(n, *fixed); }

// inverse of the function above. 
inline uint64 VariableDecode(uint32 fixed, uint64 variable) {
  return ( (1ull << fixed) + variable ) - 1; }

// Sum 10 6-bit numbers packed in the low 60 bits of a uint64.
inline uint64 CountSixes(uint64 n) {
  n = (n & 0770077007700770077ull)   + ( (n & 077007700770077007700ull) >> 6);
  n = (n & 077770000777700007777ull) + ( (n & 07777000077770000ull) >> 12);
  n = (n & 077770000000077777777ull) + ( (n & 07777777700000000ull) >> 24);
  n = (n & 07777777777777777ull)     + ( (n & 077770000000000000000ull) >> 48);
  return n; }

struct VLEncoding {

  struct Block {
    uint64 data_[8];
    /*
      A block is like a cache line. 
      We use one block for each 64 elements. 
      The block stores the fixed parts and synchronization information. 
      The things that are stored are:
        64 6-bit fixed parts
	1 44-bit block offset
	6 12-bit word offsets

      data_[0] .. data[5] store 10 fixed parts each, and 4 bits of word offset
      data_[6] stores 4 fixed parts, 36 bits of block offset, 4 bits of word offset
      data_[7] stores 7 8-bit word-offset parts and 8 bits of block offset. 
    */
    
    void SetBlockOffset(uint64 offset) { 
      data_[6] |= (offset & 0xFFFFFFFFFull) << 24; 
      data_[7] |= (offset >> 36) << 56;
    }

    uint64 GetBlockOffset() { 
      return ( (data_[6] >> 24) & 0xFFFFFFFFFull)
	| ( (data_[7] >> 56) << 36); }
    
    // Use this function to build the block.  
    // we assume these things are set in order, and the offset is passed in every time
    // pos is which of the 64 things you are. offset is the global offset of the 
    // variable bits. 
    void Set(uint32 pos, uint32 fixed_part, uint64 offset) {
      // cout << "Set " << pos << " " << fixed_part << " " << offset << endl;
      if (pos==0) {
	for (uint32 i=0; i<8; i++) data_[i] = 0;
	SetBlockOffset(offset);
      }
      uint32 tens = pos / 10;
      uint32 ones = pos % 10;
      data_[tens] |= ( ((uint64)fixed_part) << (6 * ones));
      if (ones == 0) {
	uint64 word_offset = offset - GetBlockOffset();
	// 4 bits of offset into top of data_[tens];
	data_[tens] += (word_offset & 0xFull) << 60;
	// 8 bits of offset into data_[7]	
	data_[7] |= (word_offset >> 4) << (tens * 8);
      }
    }
  };
  
  VLEncoding() {
    pass_ = 1;
  }

  void Push(uint32 n) {
    uint32 fixed_part; uint64 variable_part;
    VariableEncode(n, &fixed_part, &variable_part);
    CHECK(VariableDecode(fixed_part, variable_part) == n);

    Block & b_ref = blocks_[int_count_ / 64];

    b_ref.Set(int_count_ % 64, fixed_part, bit_count_); 

    bits_.PushRange(fixed_part, variable_part);
    // CHECK( (*this)[int_count_] == n);
    
    int_count_++;
    bit_count_ += fixed_part;
    if (int_count_ % 1000000 == 0) {
      cout << "VLEncode int_count_=" << int_count_ << " bit_count_="
	   << bit_count_ << endl;
    }
  }

  uint64 operator [] (uint64 pos) {
    Block & b_ref = blocks_[pos / 64];
    uint32 block_pos = pos % 64;
    uint32 tens = block_pos / 10;
    uint32 ones = block_pos % 10;
    
    uint32 fixed_part = 
      (b_ref.data_[tens] >> (6 * ones)) & 0x3F;

    // cout << "x= " << x << endl;
    // uint64 bit_pos = b_ref.GetBitPosition(block_pos);
    uint64 bit_pos = b_ref.GetBlockOffset() 
      + (b_ref.data_[tens] >> 60)
      + ( ( (b_ref.data_[7] >> (8 * tens)) & 0xFFull) << 4 )
      + CountSixes(b_ref.data_[tens] & ( (1ull << (ones * 6)) - 1) );
    // for (uint32 i=0; i< ones; i++) ret += (d >> (i * 6)) & 0x3F;
    
    // cout << "bit_pos = " << bit_pos << endl;
    uint64 variable_part = bits_.GetRange(bit_pos, fixed_part);
    // cout << "m= " << m << endl;
    uint64 ret =  VariableDecode(fixed_part, variable_part);
    // cout << "ret = " << ret << endl;
    return ret;
  }
  void StartBuild(uint64 max_size) {
    blocks_ = new Block[max_size / 64 + 10];
    bits_.Init(63 * max_size + 1000);
    bits_.PrepareToBuild();
    int_count_ = 0;
    bit_count_ = 0;
  }
  void EndBuild() {
    // The number of integers is stored in an extra empty block at the end. 
    size_ = int_count_;
    num_blocks_ = CeilingDiv(int_count_, 64);
    blocks_[num_blocks_].data_[0] = size_;
    memblock_ = Memblock((const char *) blocks_,
			 sizeof(Block) * (num_blocks_ + 1));    
  }
  void DistributedTouch() {
    ::DistributedTouch(memblock_.begin(), memblock_.size());
    ::DistributedTouch(bits_.block_.begin(), bits_.block_.size());
  }
  bool Load(string fn) {
    memblock_ = Mmap2(fn + ".blocks");
    if (memblock_.Fail()) return false;
    blocks_ = (Block *) memblock_.begin();
    num_blocks_ = (memblock_.size() / sizeof(Block)) - 1;
    size_ = blocks_[num_blocks_].data_[0];
    bits_.Load(fn + ".bits");
    return true;
  }
  void Store(string fn) {
    File::Write(fn + ".blocks", memblock_);
    bits_.Store(fn + ".bits");
  }
  uint64 size() { return size_;}

  
  SimpleBitArray bits_;
  Block *blocks_;
  Memblock memblock_;
  
  uint64 pass_;
  uint64 int_count_;
  uint64 bit_count_;  
  uint64 num_blocks_;

  uint64 size_;  
};

inline void TestVLEncoding(vector<uint64> & v) {
  VLEncoding enc;
  enc.StartBuild(v.size());
  for (uint64 i=0; i<v.size(); i++) enc.Push(v[i]);
  enc.EndBuild();

  for (int rep=0; rep<10; rep++) {
    for (uint64 i=0; i<v.size(); i++) 
      CHECK(enc[i] == v[i]);
    cout << "Successfully tested VL encoder " 
	 << "size_ = " << enc.size_
	 << "bit_count_ = " << enc.bit_count_ << endl;
  }
}

inline int vl_encode_main() {
  vector<uint64> v;
  for (uint64 i=0; i<10000000; i++) v.push_back(i*i);
  TestVLEncoding(v);
  return 0;

  uint64 n;

  uint32 x;
  uint64 m; 
  while (cin >> x >> m) {
    n = VariableDecode(x, m);
    VariableEncode(n, &x, &m);
    cout << n << " " << x << " " << m << endl;
  }
  
  return 0;
}

typedef SimpleCorpus Corpus;

//typedef VLEncoding Corpus;

#endif
